[HOME - BASE Cinque - Appunti di Matematica ricreativa]

Algoritmo di Euclide
per il calcolo del MCD

Questa pagina contiene programmi in javascript.
Potete salvarla sul vostro computer e utilizzarla senza essere collegati a internet.

L'algoritmo originale di Euclide, basato su sottrazioni successive

L'algoritmo per il calcolo del MCD di due interi positivi, nella sua versione più semplice, si basa sulla seguente proprietà:

Se due numeri, m, n, sono divisibili per un terzo numero, x, allora anche la loro differenza è divisibile per x.

Per dimostrarla, si può utilizzare la proprietà distributiva. Supponiamo m>n.
m=kx
n=hx
m-n=kx-hx=x(k-h)
Dunque si può dire che:

MCD(m,n) = MCD((m-n),n)

Come si vede, questa regola permette di passare, per mezzo di sottrazioni successive, a MCD di numeri sempre più piccoli, fino ad ottenere:

MCD(a,0)=a

L'algoritmo può essere scritto così:

Finché m>0
se n>m allora scambia m con n
Sottrai n da m e assegna ad m il valore della differenza (m=m-n)
Ripeti il ciclo
n è il MCD cercato

Questo algoritmo è implementato in linguaggio javascript nel riquadro qui sotto.
Potete utilizzarlo per fare degli esperimenti.
La traccia dei calcoli vi farà capire come funziona.

Calcolo del Massimo Comune Divisore di 2 numeri
Algoritmo originale di Euclide, metodo delle sottrazioni successive

Digita i due numeri nelle caselle a destra: m= n=

MCD (m,n) =

Traccia dei calcoli eseguiti

Un algoritmo più veloce, basato su divisioni successive

Euclide descrisse questo algoritmo nel suo libro degli Elementi. Invece di usare i numeri interi, però, utilizzò i segmenti di retta. Perciò il suo algoritmo serve anche a determinare il massimo comune divisore di due segmenti.
In certi casi l'algoritmo può richiedere numerosissimi passaggi, risultando molto lento (provate con MCD (900,15)).
Conviene quindi renderlo più veloce e si può fare ricorrendo ad una serie di divisioni con resto anziché sottrazioni.
Il principio su cui ci si basa è il seguente (supponiamo m>n):

MCD(m,n) = MCD(r,n)dove r è il resto della divisione m/n

Come si vede, questa regola permette di passare rapidamente, per mezzo di divisioni con resto successive, a MCD di numeri sempre più piccoli, fino ad ottenere:

MCD(r,0)=r

Questo algoritmo è implementato in linguaggio javascript nel riquadro qui sotto.
Potete utilizzarlo per fare degli esperimenti. E' molto più veloce del primo.
La traccia dei calcoli vi farà capire come funziona.
Più sotto troverete la spiegazione dettagliata.

Calcolo del Massimo Comune Divisore di 2 numeri
Algoritmo derivato da Euclide, metodo delle divisioni successive

Digita i due numeri nelle caselle a destra: m= n=  

-

MCD (m,n) = mcm (m,n)=

Traccia dei calcoli eseguiti

Combinazione lineare di m, n:   
 
Spiegazione dell'algoritmo basato sulle divisioni con resto successive
Prendiamo a,b interi con a,b>0 e supponiamo 0<a<b.
Dividiamo b per a, avremo che:
b = q1a+r1, con 0 <= r1<a.
Osserviamo che:
i) se r1=0, allora b = q1a e abbiamo già che MCD(a,b)=a;
ii) altrimenti, preso un intero positivo d
1) se d divide sia a che b, allora dividerà anche r1 in quanto combinazione lineare di a e b;
2) viceversa, se d divide a e r1, dividerà anche b per la stessa proprietà sopra.

Quindi possiamo concludere che
MCD(a,b) = MCD(a,r1),
con il vantaggio che r1<a<b.

Ora ripetiamo lo stesso procedimento sostituendo al posto di a e b i nuovi valori a e r1 con r1<a:
a = q2r1+r2 , con 0<=r2<r1
dove
i) se r2=0, si ha che r2|a, quindi MCD(a,b) = MCD(a,r1) = r2;
ii) altrimenti, si ripetono le stesse conclusioni giungendo a definire che MCD(a,b)=MCD(a,r1)=MCD(r1,r2).

Continuiamo a costruire queste successioni di resto sino ad arrivare all'i-esima iterazione dove
ri-1=qi+1ri+ri+1, con 0<=ri+1<ri
e avremo che
i) se ri=0, allora MCD(a,b) = ri-1;
ii) altrimenti, continuiamo il procedimento.

Poiché gli ri sono interi non negativi e la successione di resti è decrescente, ad un certo punto ci dovremo fermare, cioè esisterà un rn diverso da zero tale che rn+1=0, allora il nostro MCD(a,b) sarà uguale all'ultimo resto diverso da zero della catena di divisioni.
Questo procedimento è vantaggioso perché non dobbiamo scomporre in fattori primi e si utilizzano divisioni sempre più facili.
Proviamo ora a ricostruire s,t procedendo a ritroso nell'algoritmo euclideo:
presi MCD(a,b) = rn e sa+tb = rn, possiamo scrivere
rn = rn-2 - qn×rn-1,
e andiamo a sostituire il valore di rn-1 che si ricava dall'uguaglianza rn-3 = qn-1×rn-2 + rn-1:
rn = rn-2 - qn(rn-3-qn-1rn-2) = (1+qnqn-1) rn-2 - qnrn-3.
Ora sostituiamo in questa equazione il valore di rn-2 che si ottiene da rn-4 = qn-2rn-3 + rn-2 e avremo rn come espressione in rn-3 e rn-4, quindi andremo a sostituire rn-3 e continueremo questo procedimento fino ad ottenere rn come combinazione lineare dei soli a e b.

Tratto da: http://www.dm.unibo.it/matematica/Congruenze/html/pag2/pag2.htm

agosto 2004

Sito Web realizzato da Gianfranco Bo